import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class OSystem {
	private static boolean isError = false;
	public static final boolean isDebugging = false; // shows more detailed errors
	// when true.
	public static final int RUNNING = 0;
	public static final int READY_A = 1;
	public static final int BLOCKED_A = 2;
	public static final int READY_S = 3;
	public static final int BLOCKED_S = 4;

	private static int nextPid;

	private static LinkedList<PCB> readyList0; // init
	private static LinkedList<PCB> readyList1; // user
	private static LinkedList<PCB> readyList2; // system

	private static PCB currentRunningProcess; // pointer to current running proc.

	private static LinkedList<PCB> PCBList; // keep track of all PCBs in system.
	// For easier search.

	private static LinkedList<RCB> RCBList; // keep track of all RCBS in system

	/**
	 * Simulate process time out for time sharing
	 */
	public static void timeOut() {
		LinkedList<PCB> qReadyList = currentRunningProcess.getStatusList();

		qReadyList.remove(currentRunningProcess);
		currentRunningProcess.setStatusType(READY_A);
		qReadyList.addLast(currentRunningProcess);
		scheduler(currentRunningProcess);
	}

	public static PCB getRunning() {
		return currentRunningProcess;
	}

	public static void setRunning(PCB pcb) {
		currentRunningProcess = pcb;
	}

	public static void setPCB(PCB pcb) {
		currentRunningProcess = pcb;
	}

	/**
	 * Driver
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		init();

		getAndProcessCommands(sc);

		sc.close();
	}

	/**
	 * Process commands from system input
	 * 
	 * @param sc
	 */
	private static void getAndProcessCommands(Scanner sc) {
		while (sc.hasNext()) {
			String line = sc.nextLine().trim();
			String[] tokens = line.trim().split(" ");

			if (tokens[0].equals("cr")) {
				String name = tokens[1];
				int priority = Integer.valueOf(tokens[2]);
				create(priority, currentRunningProcess, name);
			} else if (tokens[0].equals("de")) {
				String name = tokens[1];
				destroy(name);
			} else if (tokens[0].equals("to")) {
				timeOut();
			} else if (tokens[0].equals("req")) {
				int rid = parseRequestId(tokens[1]);
				int nbrUnits = Integer.valueOf(tokens[2]);
				if (rid <1 || rid > 4) {
					errorMsg("Rid invalid");
				}
				else {
					request(currentRunningProcess, rid, nbrUnits);
				}
			} else if (tokens[0].equals("rel")) {
				int rid = parseRequestId(tokens[1]);
				int nbrUnits = Integer.valueOf(tokens[2]);
				if (rid <1 || rid > 4) {
					errorMsg("Rid invalid");
				}
				else {
				release(currentRunningProcess, rid, nbrUnits, false);
				}
			} else if (tokens[0].equals("init")) {
				System.out.println(); // to separate test cases
				init();
			} else {
				if (isDebugging)
					errorMsg("Error - no such command " + tokens[0]);
			}
		}
	}

	/**
	 * Used to switch between simple error messages and detailed for debugging
	 * purposes
	 * 
	 * @param msg Detailed error message
	 */
	private static void errorMsg(String msg) {
		if (isDebugging) {
			System.out.println(msg);
		} else {
			if (!isError) {
				System.out.print("error ");
			}
			isError = true;
		}

	}

	/**
	 * Initialize PCBList and RCBList, used in init()
	 */
	private static void initPcbAndRcbLists() {
		PCBList = new LinkedList<PCB>();
		RCBList = new LinkedList<RCB>();
	}

	/**
	 * Initialize ready lists, used in init()
	 */
	private static void initReadyLists() {
		readyList0 = new LinkedList<PCB>();
		readyList1 = new LinkedList<PCB>();
		readyList2 = new LinkedList<PCB>();
	}

	/**
	 * Initialize resources 1-4, used in init()
	 */
	private static void initResources() {
		for (int i = 1; i <= 4; i++) {
			RCBList.add(new RCB(i));
		}
	}

	/**
	 * Converts resource Rn to its respective rid
	 * 
	 * @param id
	 * @return
	 */
	private static int parseRequestId(String id) {
		if (id.equals("R1")) {
			return 1;
		} else if (id.equals("R2")) {
			return 2;
		} else if (id.equals("R3")) {
			return 3;
		} else if (id.equals("R4")) {
			return 4;
		} else {
			errorMsg("Error: syntax: req <R1/R2/R3/R4> <# units>");
			return -1;
		}
	}

	/**
	 * Clears existing system and Inits process
	 */
	private static void init() {
		isError = false; // turn on error msgs

		nextPid = 0;
		currentRunningProcess = null;
		readyList0 = null;
		readyList1 = null;
		readyList2 = null;
		PCBList = null;
		RCBList = null;

		// init lists
		initReadyLists();
		initPcbAndRcbLists();

		// init resources
		initResources();

		create(0, null, "init");
		currentRunningProcess = PCBList.get(0);

	}

	/**
	 * Calls destroy(int) by looking up the corresponding id of the PCB
	 * 
	 * @param name
	 */
	private static void destroy(String name) {
		Boolean isFound = false;
		for (PCB processes : PCBList) {
			if (processes.getProcessName().equals(name)) {
				destroy(processes.getPid());
				isFound = true;
				break;
			}
		}
		if (!isFound) {
			errorMsg("Error in destroy(String): unable to find matching process - "
					+ name);
		}

	}

	public static LinkedList<PCB> getReadyList0() {
		return readyList0;
	}

	public static LinkedList<PCB> getReadyList1() {
		return readyList1;
	}

	public static LinkedList<PCB> getReadyList2() {
		return readyList2;
	}

	public static int getNextPid() {
		return nextPid;
	}

	public static void incrementNextPid() {
		nextPid++;
	}

	public static void scheduler(PCB parent) {
		PCB p = null; // p is the highest priority process
		if (!readyList2.isEmpty()) {
			p = readyList2.getFirst();
		} else if (!readyList1.isEmpty()) {
			p = readyList1.getFirst();
		} else {
			p = readyList0.getFirst();
		}
		if (parent == null || parent.getPriority() < p.getPriority()
				|| parent.getStatusType() != RUNNING) {

			preempt(p, parent);

		}
		if (!isError)
			System.out.print(currentRunningProcess.getProcessName() + " ");
	}

	/**
	 * Context switch
	 * 
	 * @param p
	 * @param parent
	 */
	private static void preempt(PCB p, PCB parent) {

		if (parent != null && parent.getStatusType() == RUNNING) {
			parent.setStatusType(READY_A);
		}
		p.setStatusType(RUNNING);
		currentRunningProcess = p;

	}

	/**
	 * Create new process
	 * 
	 * @param priority
	 * @param parent
	 * @param processName
	 */
	public static void create(int priority, PCB parent, String processName) {
		PCB newProcessPCB = new PCB(priority, parent, processName);
		// check if process name already exists
		boolean isNameAlreadyExist = checkNameAlreadyExists(processName);
		if (isNameAlreadyExist) {
			errorMsg("Process name already exists!");
		} else {
			if (priority != 0) { // if not init process
				parent.getChildrenList().add(newProcessPCB);
			}

			// get readyList
			LinkedList<PCB> appropriateStatusList = getAppropriateReadyList(newProcessPCB);

			// insert new Process into RL
			appropriateStatusList.add(newProcessPCB);

			// set new process status list
			newProcessPCB.setStatusList(appropriateStatusList);

			scheduler(parent);

			// add to PCBLIST.
			PCBList.add(newProcessPCB);
		}
	}

	/**
	 * @param processName
	 * @return
	 */
	private static boolean checkNameAlreadyExists(String processName) {
		boolean isNameAlreadyExist = false;
		for (PCB process : PCBList) {
			if (process.getProcessName().equals(processName)) {
				isNameAlreadyExist = true;
			}
		}
		return isNameAlreadyExist;
	}

	/**
	 * Destroy process
	 * 
	 * @param pid Process ID
	 */
	public static void destroy(int pid) {
		PCB pcbToDestroy = findPCB(pid);

		// check if PidNotFound
		if (pcbToDestroy == null) {
			errorMsg("Destroy error: pid not found - " + pid);
		}

		// cannot destroy init
		else if (pid == 0) {
			errorMsg("Cannot destroy init");
		}

		// else PCB to destroy exists
		else {
			killTree(pcbToDestroy);
			scheduler(null);
		}

	}

	/**
	 * Find PCB given pid
	 * 
	 * @param pid
	 * @return corresponding PCB, null if not found.
	 */
	private static PCB findPCB(int pid) {
		for (PCB item : PCBList) {
			if (item.getPid() == pid) {
				return item;
			}
		}
		return null;
	}

	/**
	 * Kill tree to kill children processes, for use in destroy()
	 * 
	 * @param process
	 */
	public static void killTree(PCB process) {
		killTreeAllChildren(process);

		if (process.getStatusType() == RUNNING) {
			interrupt();
		}
		// remove from status list (either RL or a WL in RCB)
		process.getStatusList().remove(process);

		// release all other resources
		for (RCB res : process.getOtherResources()) {
			release(process, res, 1);
		}

		// Delete all pointers to PCB
		PCBList.remove(process);

	}

	/**
	 * execute killTree on all PCBs in childrenList.
	 * 
	 * @param process
	 */
	private static void killTreeAllChildren(PCB process) {
		List<PCB> childrenList = process.getChildrenList();
		for (int i = 0; i < childrenList.size(); i++) {
			killTree(childrenList.get(i));
		}
	}

	/**
	 * Interrupt current running process.
	 */
	private static void interrupt() {
		setRunning(null);
	}

	/**
	 * For use in killTree. We do not want to call scheduler in release() because
	 * it is called at end of destroy()
	 * 
	 * @param process
	 * @param res
	 * @param unitsToRelease
	 */
	private static void release(PCB process, RCB res, int unitsToRelease) {
		release(process, res.getRID(), unitsToRelease, true);

	}

	/**
	 * Release resources.
	 * 
	 * @param parent Calling PCB
	 * @param rid
	 * @param unitsToRelease
	 * @param killTree True if called from killTree(), false otherwise
	 */
	public static void release(PCB parent, int rid, int unitsToRelease,
															boolean killTree) {

		RCB rcb = getRCB(rid);

		// remove from parent.otherResources pointers to rcb (only if not called
		// from killTree())
		for (int i = 0; i < unitsToRelease; i++) {
			if (!killTree && !parent.getOtherResources().remove(rcb)) {
				errorMsg("release() error - unable to find rcb on parent.getOtherResources()");
			}
		}

		// if not called from killTree, check if released units and free units do
		// not exceed maxUnits.
		if (!killTree && (rcb.getFreeUnits() + unitsToRelease) > rcb.getMaxUnits()) {
			errorMsg("release() error - current free units + unitsToRelease > max units :"

					+ rcb.getFreeUnits() + "," + unitsToRelease + "," + rcb.getMaxUnits());

		} else {
			// update free units in rcb
			rcb.setFreeUnits(rcb.getFreeUnits() + unitsToRelease);

			// allocate resource to other processes blocked on resource's waiting list
			for (PCB proc : rcb.getWaitingList()) {
				if (proc.getOutstandingResourceRequests() <= rcb.getFreeUnits()) {
					// allocate resource
					allocateResource(rcb, proc);

				}
			}
		}
		if (!killTree) {
			scheduler(parent);
		}

	}

	/**
	 * Allocates resource to a process
	 * 
	 * @param resource
	 * @param process
	 */
	private static void allocateResource(RCB resource, PCB process) {
		int unitsRequested = process.getOutstandingResourceRequests();

		process.setOutstandingResourceRequests(0);

		addResourceUnitsToOtherResources(process, unitsRequested, resource);

		// deduct free units from rcb
		resource.setFreeUnits(resource.getFreeUnits() - unitsRequested);

		// remove proc from waiting list
		resource.getWaitingList().remove(process);
		// change proc status
		if (process.getStatusType() == BLOCKED_A) {
			process.setStatusType(READY_A);
		} else {
			process.setStatusType(READY_S);
		}
		// add proc to RL
		LinkedList<PCB> procRL = getAppropriateReadyList(process);
		process.setStatusList(procRL);
		procRL.add(process);
	}

	/**
	 * Returns appropriate readyList according to its priority. Returns null if
	 * priority not within 0-2
	 * 
	 * @param process
	 */
	private static LinkedList<PCB> getAppropriateReadyList(PCB process) {
		int processPriority = process.getPriority();
		if (processPriority == 0) {
			return readyList0;
		}
		if (processPriority == 1) {
			return readyList1;
		}
		if (processPriority == 2) {
			return readyList2;
		}
		return null;
	}

	/**
	 * return RCB given rid
	 * 
	 * @param rid
	 * @return
	 */
	private static RCB getRCB(int rid) {
		for (RCB rcb : RCBList) {
			if (rcb.getRID() == rid) {
				return rcb;
			}
		}
		errorMsg("ERROR: getRCB() :RCB not found");
		return null;
	}

	/**
	 * Request()
	 * 
	 * @param parent calling process
	 * @param rid Resource ID
	 * @param requestedUnits Number of units requested by parent
	 */
	public static void request(PCB parent, int rid, int requestedUnits) {
		RCB resource = getRCB(rid);

		// get no. of resources already allocated to that particular resource
		int allocatedResourceCount = countAlreadyAllocatedResources(parent, rid);

		if (requestedUnits > resource.getMaxUnits()) {
			errorMsg("ERROR: request() requestUnits > rcb.maxUnits");
		} else if (parent.getPid() == 0) {
			errorMsg("Illegal op: Init processes cannot request");
		} else if ((requestedUnits + allocatedResourceCount) > rid) {
			errorMsg("Requested units + already allocated units exceed Resource capacity - "
					+ rid + " " + (requestedUnits + allocatedResourceCount));
		} else {
			if (requestedUnits <= resource.getFreeUnits()) {
				// allocate resource

				resource.setFreeUnits(resource.getFreeUnits() - requestedUnits);
				// add to PCB.otherResources
				addResourceUnitsToOtherResources(parent, requestedUnits, resource);

			} else {
				// block process
				parent.setOutstandingResourceRequests(requestedUnits);
				parent.getStatusList().remove(parent);
				parent.setStatusType(BLOCKED_A);
				parent.setStatusList(resource.getWaitingList());

				resource.getWaitingList().add(parent);

			}
			scheduler(parent);
		}

	}

	/**
	 * @param parent
	 * @param rid
	 * @return
	 */
	private static int countAlreadyAllocatedResources(PCB parent, int rid) {
		int allocatedResourceCount = 0;
		for (int i = 0; i < parent.getOtherResources().size(); i++) {
			if (parent.getOtherResources().get(i).equals(getRCB(rid))) {
				allocatedResourceCount++;
			}
		}
		return allocatedResourceCount;
	}

	/**
	 * For use in request() to add RCB pointer to PCB.otherResources
	 * requestedUnits times.
	 * 
	 * @param parent Calling process
	 * @param requestedUnits
	 * @param resource
	 */
	private static void addResourceUnitsToOtherResources(PCB parent,
																												int requestedUnits,
																												RCB resource) {
		for (int i = 0; i < requestedUnits; i++) {
			parent.getOtherResources().add(resource);
		}
	}

}
